/*
 * Creado el 06/11/2011
 */

package fpuna.ia.ea.moaco;

import java.util.Random;
import java.util.Iterator;

import fpuna.ia.ea.FrentePareto;
import fpuna.ia.ea.Punto;
import fpuna.ia.ea.instancia.Instancia;

/**
 *
 * @author gusamasan
 */
public class MOACSTSP {
// -----------------------------------------------------------------------------

    public static int NO_ACCESIBLE  = -1;
    public static int INFINITO      = 10000;

    private double      beta, lambda, qInicial, rho, tInicial, feromanaT[][];

    private double mDistancias[][]  ,
                   mObjetivo1[][]   ,
                   mObjetivo2[][]   ,
                   tau;

    private int         ciudadInicio                ,
                        cantidadCiudades            ,
                        cantidadHormigas            ,
                        cantidadMaximaGeneraciones  ,
                        generacion                  ,
                        indiceActual                ,
                        vectorActual[];


    private Instancia   intanciaProblema;

    private Random      numerSeudoAleatorio;

    private FrentePareto    frentePareto;

    private Punto       nuevoPunto;

// -----------------------------------------------------------------------------

    /** Constructores *********************************************************/
    public MOACSTSP(){
    }
    /**************************************************************************/


    private void actualizarConjuntoPareto(){
    // ----------------------------------------------------------------------

        int indice, vectorSolucion[];

    // ----------------------------------------------------------------------

        vectorSolucion  = new int[ this.cantidadCiudades ];
        
        for( indice=0; indice < this.cantidadCiudades; indice++ ){
            vectorSolucion[ indice ] =  this.vectorActual[ indice ];
        }

        this.nuevoPunto.setSolucion( vectorSolucion );
        
        this.frentePareto.agregarSiNoDominado( this.nuevoPunto );
    }

    private void actualizarFeromonasParaCadaSolucion( double productoValoresPromedios ){
    // ------------------------------------------------------------------------

        int indice, i, j, limite, solucion[];

        double tau;

        Iterator puntosFrente;

        Punto   unPunto;

    // ------------------------------------------------------------------------


        puntosFrente = this.frentePareto.obtenerPuntosFrente();

        while( puntosFrente.hasNext() ){

            unPunto     = (Punto)puntosFrente.next();

            solucion    = unPunto.getSolucion();

            i           = this.ciudadInicio;
            limite      = this.cantidadCiudades;

            for( indice= 1; indice < limite; indice++ ){
                j                           = solucion[ indice ];

                tau                         = this.feromanaT[ i ][ j ];
                tau                         = ( 1 - rho)*tau;
                tau                         = tau + this.rho/productoValoresPromedios;

                this.feromanaT[ i ][ j ]    = tau;

                i                           = j;
            }

            
        }

    }
    
    private void actualizarFeromonas(){
    // -------------------------------------------------------------------------


        double tPrima, productoValoresPromedios;

    // -------------------------------------------------------------------------

        productoValoresPromedios    = this.frentePareto.obtenerProductoValoresPromedios();

        tPrima                      = 1/productoValoresPromedios;

        if( tPrima > this.tInicial ){
            this.tInicial   = tPrima;

            this.inicializarMatrizFeromonas();
        }
        else{
            this.actualizarFeromonasParaCadaSolucion( productoValoresPromedios );
        }
        
    }

    public void buscarConjuntoPareto(){
    // ------------------------------------------------------------------------

        int hormiga;

    // ------------------------------------------------------ ------------------

        this.inicializarParametros();
        
        while( !condicionParada() ){
            this.generacion++;
            
            for( hormiga=0; hormiga < this.cantidadHormigas; hormiga++ ){
                
                this.lambda = (hormiga + 1)/this.cantidadHormigas;

                this.construirSolucion();       

                this.evaluarSolucion();

                //this.nuevoPunto.imprimirEvaluaciones();

                this.actualizarConjuntoPareto();
                
                this.actualizarFeromonas();

                
            }
        }

        this.frentePareto.imprimirFrente();
    }

    private boolean condicionParada(){
    // -------------------------------------------------------------------------

    // -------------------------------------------------------------------------

        return( this.generacion > cantidadMaximaGeneraciones );
    }

    private boolean fueVisitado( int estadoJ ){
    // ------------------------------------------------------------------------

        int indice;

    // ------------------------------------------------------------------------

        for( indice=0; indice <= this.indiceActual; indice++ ){
            if( this.vectorActual[ indice ] == estadoJ ){
                return( true );
            }                
        }

        return( false );
    }

    private int obtenerSiguientePorMaximo(){
    // ----------------------------------------------------------------------

        int estadoI, estadoJ, vecino;
        double visibilidadUno, visibilidadDos   ,
                valorVecino, maximo;

    // ----------------------------------------------------------------------

        estadoI = this.vectorActual[ this.indiceActual ];

        estadoJ = MOACSTSP.NO_ACCESIBLE;

        maximo  = -MOACSTSP.INFINITO;

        for( vecino= 0; vecino < this.cantidadCiudades; vecino++ ){
            if( !this.fueVisitado( vecino ) ){

                visibilidadUno  = this.mObjetivo1[ estadoI ][vecino]; // en realidad, ya se eleva a las potencias correspondientes
                visibilidadUno  = Math.pow( visibilidadUno, this.lambda*this.beta );

                visibilidadDos  = this.mObjetivo1[ estadoI ][vecino]; // en realidad, ya se eleva a las potencias correspondientes
                visibilidadDos  = Math.pow( visibilidadDos, ( 1 - this.lambda )*this.beta );

                valorVecino = this.feromanaT[ estadoI ][ vecino ]*visibilidadUno*visibilidadDos;

                if( valorVecino > maximo ){
                    estadoJ = vecino;
                    maximo  = valorVecino;
                }
            }
        }

        return( estadoJ );
    }

    private double obtenerValorVecino( int estadoI, int vecino ){
    // ------------------------------------------------------------------------

        double valorVecino,
               visibilidadUno, visibilidadDos;

     // ------------------------------------------------------------------------

        visibilidadUno  = this.mObjetivo1[ estadoI ][vecino]; // en realidad, ya se eleva a las potencias correspondientes
        visibilidadUno  = 1/visibilidadUno;
        visibilidadUno  = Math.pow( visibilidadUno, this.lambda*this.beta );

        visibilidadDos  = this.mObjetivo1[ estadoI ][vecino]; // en realidad, ya se eleva a las potencias correspondientes
        visibilidadDos  = 1/visibilidadDos;
        visibilidadDos  = Math.pow( visibilidadDos, ( 1 - this.lambda )*this.beta );

        valorVecino = this.feromanaT[ estadoI ][ vecino ]*visibilidadUno*visibilidadDos;

        return( valorVecino );
    }

    private int obtenerSiguientePorRuleta(){
    // ----------------------------------------------------------------------

        int estadoI, indice, vecino;

        double torta, valorVecino;

        double ruleta[][];

    // ----------------------------------------------------------------------

        ruleta                  = new double[2][this.cantidadCiudades];

        estadoI                 = this.vectorActual[ this.indiceActual ];

        torta                   = 0;

        indice                  = 0;

        // Se construye la torta y registra el pedazo correspondiente
        // a cada vecino

        for( vecino=0; vecino < this.cantidadCiudades; vecino++ ){

            if( !this.fueVisitado(vecino) ){
                
                valorVecino = this.obtenerValorVecino(estadoI, vecino);
                
                torta+= valorVecino;

                ruleta[ 0 ][ indice ] = valorVecino;
                ruleta[ 1 ][ indice ] = vecino;

                indice++;
            }
        }

        // Lanzamiento de la ruleta

        torta   = this.numerSeudoAleatorio.nextDouble()*torta;
        
        while( --indice >= 0 ){

            torta   = torta - ruleta[ 0 ][ indice ];

            if( torta < 0 )
                return( (int)ruleta[1][ indice ] );
        }

        return( MOACSTSP.NO_ACCESIBLE );
    }

    private int buscarSiguienteEstado(){
    // ------------------------------------------------------------------------

        double q;
        int estadoJ;
        
    // ------------------------------------------------------------------------


        q       = this.numerSeudoAleatorio.nextDouble();

        if( q < this.qInicial ){
            estadoJ = this.obtenerSiguientePorMaximo();
        }
        else{
            estadoJ = this.obtenerSiguientePorRuleta();
        }

        return( estadoJ );
    }

    private void construirSolucion(){
    // ------------------------------------------------------------------------

        int cantidadEstados ,
            estadoI         ,
            estadoJ         ,
            indice          ,
            vectorSolucion[];

        
    // ------------------------------------------------------------------------


        mDistancias     = this.intanciaProblema.obtenerMDistancias();
        mObjetivo1      = this.intanciaProblema.obtenerMObjetivoUno();
        mObjetivo2      = this.intanciaProblema.obtenerMObjetivoDos();

        estadoI         = this.ciudadInicio;
        cantidadEstados = this.intanciaProblema.obtenerCantidadCiudades();

        //vectorSolucion  = new int[ cantidadEstados ];

        this.indiceActual= 0;
        //vectorSolucion[ this.indiceActual ] = estadoI;
        this.vectorActual[ this.indiceActual ] = estadoI;


        while( indiceActual < cantidadEstados ){
            estadoJ = this.buscarSiguienteEstado();

            if( estadoJ != MOACSTSP.NO_ACCESIBLE ){

                // Actualización paso a paso de feromonas
                this.tau                        = feromanaT[ estadoI ][ estadoJ ];
                this.tau                        = ( 1 - this.rho )*this.tau + this.rho*this.tau;
                feromanaT[ estadoI ][ estadoJ ] = this.tau;

                // Agregando el siguiente estado
                this.indiceActual++;

                this.vectorActual[ this.indiceActual ] = estadoJ;                

                //this.imprimirSolucion();
                
                if( this.indiceActual == ( this.cantidadCiudades - 1 ) ){

                    //System.out.println( "j: " + estadoJ + "  inicio: " + this.ciudadInicio );
                    
                    if( this.mObjetivo1[ estadoJ ][ this.ciudadInicio ] > 0.0 )
                        break;
                    else
                        this.indiceActual = this.indiceActual - 2;

                }

                //System.out.println( "" + 100*(this.indiceActual + 1 )/this.cantidadCiudades );
            }
            else
                this.indiceActual--;


            if( this.indiceActual < 0  ){
                System.out.println( "ERROR" );
                break;
            }

            estadoI = this.vectorActual[ this.indiceActual ];
        }


    }

    private void evaluarSolucion(){
    // ------------------------------------------------------------------------

        int indice, limite, i, j;

        double resultadoObjetivo;

    // ------------------------------------------------------------------------

        this.nuevoPunto          = new Punto( 2 );
        limite              = this.cantidadCiudades;

        // Calculando resultado para el objetivo 1
        i                   = this.ciudadInicio;
        resultadoObjetivo   = 0.0;
        for( indice=1; indice < limite; indice ++ ){
            j   = this.vectorActual[ indice ];
            
            resultadoObjetivo+= this.mObjetivo1[ i ][ j ];

            i   = j;
        }

        resultadoObjetivo+= this.mObjetivo1[ i ][ this.ciudadInicio ];

        this.nuevoPunto.asignarValorObjetivo( Punto.INDICE_OBJETIVO_UNO, resultadoObjetivo );

        // Calculando resultado para el objetivo 2
        i                   = this.ciudadInicio;
        resultadoObjetivo   = 0.0;
        
        for( indice=1; indice < limite; indice ++ ){
            j   = this.vectorActual[ indice ];

            resultadoObjetivo+= this.mObjetivo2[ i ][ j ];

            i   = j;
        }

        resultadoObjetivo+= this.mObjetivo1[ i ][ this.ciudadInicio ];

        this.nuevoPunto.asignarValorObjetivo( Punto.INDICE_OBJETIVO_DOS, resultadoObjetivo );
        
        //nuevoPunto.imprimirEvaluaciones();
    }

    private void inicializarMatrizFeromonas(){
    // ----------------------------------------------------------------------

        int fila, columna;

    // ----------------------------------------------------------------------
        
        for( fila=0; fila < cantidadCiudades; fila++ ){
            for( columna=0; columna < cantidadCiudades; columna++ ){
                this.feromanaT[ fila ][ columna ] = this.tInicial;
            }
        }
    }

    private void inicializarParametros(){
    // ----------------------------------------------------------------------

    // ----------------------------------------------------------------------

        this.ciudadInicio       = 0;
        this.cantidadHormigas   = 20;
        this.generacion         = 1;
        this.lambda             = 0; // Se inicializa dependiendo de la hormiga k/m
        this.beta               = 0.5;
        this.qInicial           = 0.6;
        this.rho                = 0.7;

        this.cantidadMaximaGeneraciones = 100;

        // ********************************************************************
        this.tInicial           = 0.0001;
        // ********************************************************************

        numerSeudoAleatorio     = new Random();
        this.frentePareto       = new FrentePareto();
        
        this.intanciaProblema   = new Instancia();
        this.intanciaProblema.cargarInstanciaTSP( Instancia.ARCHIVO_KROAC100_TSP );

        cantidadCiudades        = this.intanciaProblema.obtenerCantidadCiudades();

        this.feromanaT          = new double[ cantidadCiudades ][ cantidadCiudades ];
        this.vectorActual       = new int[ this.cantidadCiudades ];


        this.inicializarMatrizFeromonas();
        
    }

    public void imprimirSolucion(){
    // ------------------------------------------------------------------------

        int indice;

    // ------------------------------------------------------------------------

        for( indice=0; indice < this.cantidadCiudades; indice++ )
            System.out.print( this.vectorActual[ indice ] + "," );

        System.out.println( "" );
    }

    public static void main( String argv[] ){
    // ----------------------------------------------------------------------

        MOACSTSP moacs;

    // ----------------------------------------------------------------------

        moacs = new MOACSTSP();

        moacs.buscarConjuntoPareto();        
    }
}
